package book_mianshizhinan.test1_10;

import java.util.LinkedList;

public class GetNum {

	public static void main(String[] args) {

		int[] arr = {
			1,3,2	
		};
		System.out.println(getNum(arr, 2));
	}

	public static int getNum(int[] arr, int num) {

		int res = 0;
		LinkedList<Integer> qmin = new LinkedList<Integer>();
		LinkedList<Integer> qmax = new LinkedList<Integer>();

		int i = 0;
		int j = 0;
		while (i < arr.length) {
			while (j < arr.length) {

				if (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[j]) {
					qmin.pollLast();
				}
				qmin.addLast(j);

				if (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[j]) {
					qmax.pollLast();
				}
				qmax.addLast(j);

				if ((arr[qmax.peekFirst()] - arr[qmin.peekFirst()]) > num) {
					break;
				}
				j++;

			}

			if (qmin.peekFirst() == i) {
				qmin.pollFirst();
			}
			if (qmax.peekFirst() == i) {
				qmax.pollFirst();
			}

			res += j - i;// 为什么不是j-i+1呢，因为J不是arr.length，就是比符合规则的j多1.所以不用加1
			i++;

		}

		return res;
	}

}
